package com.yequan.leetcode.greedy.jump_45;

/**
 * //给定一个非负整数数组，你最初位于数组的第一个位置。
 * //
 * // 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * //
 * // 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * //
 * // 示例:
 * //
 * // 输入: [2,3,1,1,4]
 * //输出: 2
 * //解释: 跳到最后一个位置的最小跳跃数是 2。
 * //     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
 * //
 * //
 * // 说明:
 * //
 * // 假设你总是可以到达数组的最后一个位置。
 * // Related Topics 贪心算法 数组
 *
 * @author : Administrator
 * @date : 2020/4/12
 */
public class Jump {

    public static void main(String[] args) {
        int[] nums = {2, 3, 1, 1, 4};
        Jump jump = new Jump();
        int ans = jump.jump1(nums);
        System.out.println(ans);
    }

    public int jump1(int[] nums) {
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPosition = Math.max(maxPosition, nums[i] + i);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    /**
     * 贪心算法
     * 每次跳跃动取最大的跳跃数
     * 判断下一次跳跃点,再进行跳跃,直到遍历完整个数组
     */
    public int jump2(int[] nums) {
        int step = 0;
        int maxPos = 0;
        int next = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPos = Math.max(maxPos, nums[i] + i);
            if (i == next) {
                next = maxPos;
                step++;
            }
        }
        return step;
    }

    public int jump3(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int maxPoint = 0;
        int step = 0;
        int nextIndex = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPoint = Math.max(maxPoint, nums[i] + i);
            if (i == nextIndex) {
                nextIndex = maxPoint;
                step++;
            }
        }
        return step;
    }

    public int jump4(int[] nums) {
        int maxPoint = 0;
        int step = 0;
        int nextIndex = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPoint = Math.max(nums[i] + i, maxPoint);
            if (i == nextIndex) {
                step++;
                nextIndex = maxPoint;
            }
        }
        return step;
    }

    public int jump5(int[] nums) {
        int step = 0;
        int maxPoint = 0;
        int nextIndex = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            maxPoint = Math.max(maxPoint, nums[i] + i);
            if (i == nextIndex) {
                step++;
                nextIndex = maxPoint;
            }
        }
        return step;
    }
}
